/*
 * @lc app=leetcode.cn id=628 lang=cpp
 *
 * [628] 三个数的最大乘积
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    int maximumProduct(vector<int> &nums)
    {
        std::sort(nums.begin(), nums.end());
        int index0 = nums.size();
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] >= 0)
            {
                index0 = i;
                break;
            }
        }

        if (index0 >= 2 && index0 < nums.size())
        {
            int tmp1 = nums[nums.size() - 1] * nums[0] * nums[1];
            int tmp2 = nums[nums.size() - 1] * nums[nums.size() - 2] * nums[nums.size() - 3];
            return std::max(tmp1, tmp2);
        }

        index0 = nums.size();

        return nums[index0 - 1] * nums[index0 - 2] * nums[index0 - 3];
    }
};

// int main(int argc, char const *argv[])
// {
//     vector<int> v = {-710, -107, -851, 657, -14, -859, 278, -182, -749, 718, -640, 127, -930, -462, 694, 969, 143, 309, 904, -651, 160, 451, -159, -316, 844, -60, 611, -169, -73, 721, -902, 338, -20, -890, -819, -644, 107, 404, 150, -219, 459, -324, -385, -118, -307, 993, 202, -147, 62, -94, -976, -329, 689, 870, 532, -686, 371, -850, -186, 87, 878, 989, -822, -350, -948, -412, 161, -88, -509, 836, -207, -60, 771, 516, -287, -366, -512, 509, 904, -459, 683, -563, -766, -837, -333, 93, 893, 303, 908, 532, -206, 990, 280, 826, -13, 115, -732, 525, -939, -787};
//     cout << Solution().maximumProduct(v) << endl;
//     return 0;
// }

// @lc code=end
